1. Field of the Invention
The present invention relates generally to digital communication systems that use error correcting codes and, more particularly, to decoders for error correcting codes used in digital communication systems.
2. Description of Related Art
Digital communication systems provide increased robustness to noise and other impairments during propagation compared to analog communication systems. The robustness to noise and other impairments may be further improved in digital communication systems by the use of error correcting codes. Error correcting codes are commonly used in digital communication systems for improving the performance of the system in terms of reduced error rate and/or reduced signal to noise ratio (“SNR”). Error correcting codes introduce redundancy, in a controlled manner, to the data prior to transmission. At the receiver, the structure of the error correcting code and the redundancy in the received data are used to detect and/or correct identified errors.
FIG. 1 shows an exemplary block diagram of a digital communication system 100 that uses error correcting codes. In FIG. 1, the blocks such as the encoder 102, interleaver 104 and modulator 106 are shown as part of a transmit entity 108. The other blocks of the transmit entity 108 such as a controller, data converters, etc., are not shown. In FIG. 1, the blocks such as demodulator 110, deinterleaver 112 and decoder 114 are shown as part of a receive entity 116. The other blocks of the receive entity 116 such as a controller, data converters, etc. are not shown. As used herein, the terms “transmit entity” and “transmitter” are used interchangeably and the terms “receive entity” and “receiver” are also used interchangeably.
At the transmit entity 108, the input data from an information source may be encoded by encoder 102 implementing an error correcting code. In some systems the input data to the encoder of an error correcting code may include an error detection mechanism such as cyclic redundancy code (“CRC”). The encoded data may be further processed before transmission. Often the encoded data may be interleaved to guard against burst errors. The interleaved data is generally modulated by modulator 106 before transmission.
In some communication systems, encoding and modulation may be performed jointly, for example, systems that use Trellis Coded Modulation (“TCM”). The transmitted data may be corrupted by noise and other impairments as it propagates through the communication channel 118. At the receive entity 116, the received data may be processed before passing on to the decoder 114 for error correction. The processing may include demodulating the received data by demodulator 110 and deinterleaving the demodulated data by the deinterleaver 112. The output of the decoder 114 is provided to the other subsystems of the communication system for further processing. For example, the output of the decoder may be checked for its correctness by verifying its CRC.
In general, there are two classes of methods for error correction, namely Forward Error Correction (“FEC”) and Automatic Repeat Request (“ARQ”). In a FEC process, the receiver uses the received encoded data and all the information available about the error correction code used by the transmit entity to detect and correct errors that may be present in the received data. In an ARQ process, the receiver detects the errors that may be present in the received data and, if necessary, requests the transmit entity for retransmission to correct the errors. The encoder of FEC error correction method is referred as an FEC encoder and the decoder of an FEC error correction method to detect and correct errors is referred as an FEC decoder.
The data transferred between the transmit entity 108 and the receive entity 116 may represent different types of information such as voice, images, video, computer data, etc. Different types of information is digitized and represented as a bit stream. It is to be understood that the data being transferred between the transmit entity 108 and the receive entity 116 may take different representations during transmission. However, the data at the input of the FEC encoder at the transmit entity 108 is normally a stream of bits and the data at the output of the FEC decoder at the receive entity 116 is normally a stream of bits.
The input and output of an FEC encoder are in the form of bits. In some communication systems, the output of the FEC encoder is mapped to symbols chosen from a constellation of the modulation technique used. For example, a communication system may use Quadrature Phase Shift Keying (“QPSK”) modulation. A QPSK constellation is shown in FIG. 2. For the chosen example in FIG. 2, each symbol in the constellation is associated with a group of two bits (i.e., 00, 01, 10 or 11). The output of the interleaver, for example, may be grouped into two-bit vectors and these two-bit vectors may be used to select one of the four symbols from the constellation by the modulator.
The modulated symbol is transmitted through the communication channel. The received symbol at the receiver may be different from the transmitted symbol because as the symbol passes through the propagation channel 118 it may experience different impairments such as fading or multipath interference. At the receiver, the received symbol is processed by the demodulator. The demodulator determines the most likely transmitted symbol based on the received symbol.
The demodulator may operate in a hard decision mode or a soft decision mode when determining the most likely transmitted symbol and its associated bits based on the received symbol. In hard decision mode, the demodulator outputs the exact bit pattern associated with the most likely symbol based on the received symbol. In soft decision mode, the demodulator outputs the likelihood or probability of each bit being a one or a zero. The output of the demodulator in hard decision mode is referred to as “hard bits” whereas the output of the demodulator in soft decision mode is referred to as “soft bits” or “soft metrics.”
Soft metric represents the degree of confidence the demodulator has about the value of each bit. The FEC decoder may use this likelihood information during the decoding process. Generally a communication system designed with a demodulator and FEC decoder operating in soft decision mode may provide superior performance than a communication system designed with demodulator and FEC decoder operating in hard decision mode.
Convolutional codes and Turbo codes are two commonly used coding schemes. Convolutional codes are normally specified by a constraint length K of the code, the rate of the code, and generator polynomials. The rate of the code is defined as the ratio of number of input bits to the number of output bits per encoding operation. The generator polynomials specify the connections between different shift register outputs to the adders that generate output bits.
An example of an encoder with constraint length K=3 and rate ½ convolutional code is shown in FIG. 3. For each input bit to the encoder, there are two output bits, namely output bits X and Y as shown in FIG. 3. After encoding each input bit, the content of register s1 is shifted into register s0 and the next input bit is shifted into register s1. The X output bits and Y output bits may be multiplexed into a single stream of bits for further processing such as puncturing, interleaving and modulation at the transmitter. FIG. 3 shows a feed-forward structure of a convolutional code.
Convolutional codes may also be generated using a feedback structure as shown in FIG. 4. Convolutional codes generated using a feedback structure are also referred to as “recursive convolutional codes.” When the original input bits are explicitly included without modification into the encoded output bit stream by a code, then the code is referred to as “systematic code.” When the original input bits are not explicitly included in the output stream by a code, then the code is referred to as “non-systematic code.” The code used by the encoder shown in FIG. 3 is a non-systematic code whereas the code used by the encoder shown in FIG. 4 is a systematic code. The code used by the encoder in FIG. 4 also has a recursive structure and therefore it may be referred to as a Recursive Systematic Code (“RSC”).
FIG. 5 illustrates a turbo encoder. The Turbo encoder as shown in FIG. 5 includes a constituent encoder and a turbo interleaver. The constituent encoder may be an FEC encoder such as a convolutional encoder. The input bits to the Turbo encoder are encoded twice as follows. First the input bits are encoded in the same order as they are received, referred to as “normal order,” by connecting the switch SW in FIG. 5 to Position 1. When the switch SW is in Position 1, the output bits of the constituent encoder are referred to as parity 1 bits. The Turbo interleaver re-arranges the input bits in a pre-defined manner.
Next the interleaved bits, referred to as “interleaved order,” are encoded by connecting the switch SW in FIG. 5 to Position 2. When the switch SW is in Position 2, the output bits of the constituent encoder are referred to as parity 2 bits. The normal order input bits are referred to as systematic bits. The systematic bits are grouped with Parity 1 bits and Parity 2 bits for further processing before transmission. Typically, Turbo codes use RSC codes when convolutional codes are used as constituent codes.
Two commonly used decoding methods for convolutional codes are Viterbi decoding and Maximum A-posteriori Probability (“MAP”) decoding. The two different decoding methods are suitable for different applications. Normally the Viterbi decoder accepts soft bits as input and produces hard decision in the form of bits as output. When convolutional codes are used as constituent codes for Turbo codes, the decoders used for convolutional codes may also be used for decoding Turbo codes.
The FEC decoder for Turbo codes is referred to as a Turbo decoder. Turbo decoders may be implemented using different decoding methods depending on the constituent encoder. For a Turbo encoder that uses a convolutional encoder as a constituent encoder, the Turbo decoder may be implemented using MAP decoder, Soft Output Viterbi Algorithm (“SOVA”) decoder, etc. The MAP decoder and two of its variants referred to as the Logarithmic-MAP (“Log-MAP”) decoder and the Maximum-Logarithmic-MAP (“Max-Log-MAP”) decoder are commonly used decoders for decoding Turbo codes.
The received data at the Turbo decoder corresponding to the Turbo encoder shown in FIG. 5 is demultiplexed into systematic bits, parity 1 bits and parity 2 bits and are in the form of soft bits. The received data is organized into two sets. One set of data referred to as “Normal data set,” is formed by the systematic bits and parity 1 bits. The second set of data referred to as “Interleaved data set,” is formed by the systematic bits and parity 2 bits.
The MAP decoder operates on one data set at a time, either the Normal data set or the Interleaved data set. Performing one MAP decoding operation on one data set is referred herein as an iteration. Turbo decoding consists of successive MAP decoding operations on the Normal data set and on the Interleaved data set alternately. This iterative process improves the probability of correct decision. The Turbo decoding process is illustrated by the functional block diagram as shown in FIG. 6.
The Turbo decoder generally stops processing the received data either after performing a predetermined number of iterations or when some adaptive stopping criteria are met. For example, after each iteration, the minimum absolute value of likelihood ratios as described below may be checked against an empirically determined threshold. If it is above the empirically determined threshold, then the Turbo decoder may stop performing further iterations. The final likelihood ratios of the iterative decoding process are used to make the hard decision about the binary value of the decoded bits.
The operation of the MAP decoder is illustrated by using an example of a convolutional code as the constituent code for the Turbo encoder. The MAP decoder operates according to the trellis structure of the constituent code used by the transmitter. The trellis structure details all possible state transitions of the encoder for a given input symbol and the current state of the encoder.
FIG. 7 illustrates an example of a 4-state trellis structure with 16 stages. The states of the encoder are represented by solid circles in a trellis diagram as shown in FIG. 7. The transitions between different states are shown by lines. A stage represents the transition caused by one or more input bits to the encoder from one state to another state. For a general discussion of trellis diagrams and FEC, see Viterbi, “CDMA—Principles of Spread Spectrum Communication,” ©1995, Addison-Wesley Publishing Co., e.g., §5.3.
The MAP decoder computes the estimate of the likelihood for an output bit at a given stage to be one or zero based on the soft bits corresponding to that stage and all the other soft bits before that stage and after that stage. The output of the MAP decoder is generally the decoded bits expressed as likelihood ratios, i.e., the ratio of probability of a particular bit being a one to the probability of that bit being a zero. When decoding convolutional codes using MAP decoder, the likelihood ratios may be used for determining the decoded bits. When decoding Turbo codes using MAP decoder, the likelihood ratios may be used for performing further steps of Turbo decoding.
The likelihood ratios are computed by the MAP decoder using state metrics which are referred to as α state metrics and β state metrics for a given stage in the trellis as shown in FIG. 7. The α state metric for a given state represents the probability of the encoder to be in that state for that stage in the trellis based on all the received data before that stage. The β state metric for a given state represents the probability of the encoder to be in that state for that stage in the trellis based on all the received data after that stage. The number of α state metrics and β state metrics computed at each stage in the trellis is equal to the number of states in the trellis. Computation of α state metrics through the trellis is normally referred to as “Forward recursion” and computation of β state metrics through the trellis is normally referred to as “Backward recursion.”
At the receiver, the MAP decoder computes the α state metrics as follows. A branch metric corresponding to a branch that connects two states at a given stage in a trellis is a measure for the likelihood that this branch was taken at the encoder given the received data. For each stage, the MAP decoder computes all possible branch metrics. There are two or more branches merging at each state in a trellis. At a given stage n, the transition probabilities for a branch may be computed by adding the branch metric for the branch merging into a state and the state metric corresponding to the state from which the branch originates at stage n−1. The state metric of a given state at stage n is the sum of the transition probabilities of all the branches merging into that state. The β state metrics may be computed in the same way by traversing the trellis in the backward direction.
The computation of likelihood ratios at a given stage requires both α state metrics and β state metrics for that stage. According to a traditional MAP decoding method, first the α state metrics may be computed using Forward recursion and then β state metrics may be computed using Backward recursion. As the Backward recursion is progressing, since α state metrics for all the stages may be available, the likelihood ratios may be computed simultaneously along with β state metrics computations. Therefore, two separate recursions may be required for one complete MAP decoding operation.
According to another traditional MAP decoding method, first the β state metrics may be computed using Backward recursion and then α state metrics may be computed using Forward recursion. As the Forward recursion is progressing, since β state metrics for all the stages may be available, the likelihood ratios may be computed simultaneously along with α state metrics computation. Therefore, again two separate recursions may be required for one complete MAP decoding operation. In general, for the traditional MAP decoding methods, two separate recursions may be required for one complete MAP decoding operation.
Normally multiple MAP decoding operations may be performed in Turbo decoding on both the Normal data set and the Interleaved data set. Generally larger the number of iterations better the decoding performance for a Turbo decoder. Normally the number of iterations may be chosen depending on the required complexity and performance tradeoff. Normally four to eight iterations may be performed on both the Normal data set and the Interleaved data set. When using eight iterations for a Turbo decoder using a traditional MAP decoding method, there may be 16 MAP decoding operations and this may result in 32 recursions.
Normally, Turbo codes offer improved performance. However, decoders of Turbo codes may have increased latency due to the iterative decoding nature. Furthermore, for high data rate communication systems, the required throughput of the Turbo decoder may be very high. For example, a communication system such as a Wireless Local Area Networks (“WLAN”) uses data rates of up to 108 megabits per second. Therefore, new methods and architectures for Turbo decoding that may offer increased throughput and lower latency are highly desirable. Since a MAP decoder is the main part of a Turbo decoder, new methods and architectures for MAP decoders that may offer increased throughput, lower latency and reduced power consumption are highly desirable for high data rate communication systems.